package com.leecode;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 79. 单词搜索
 *
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母不允许被重复使用。
 * 示例:
 * @formatter:off
 * board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 * @formatter:on
 * 给定 word = "ABCCED", 返回 true
 * 给定 word = "SEE", 返回 true
 * 给定 word = "ABCB", 返回 false
 * 提示：
 *     board 和 word 中只包含大写和小写英文字母。
 *     1 <= board.length <= 200
 *     1 <= board[i].length <= 200
 *     1 <= word.length <= 10^3
 */
public class Leet79 {
	public static void main(String[] args) {
		char[][] board = new char[][]{
				{'A', 'B', 'C', 'E'},
				{'S', 'F', 'C', 'S'},
				{'A', 'D', 'E', 'E'}
		};
		new Leet79().exist(board, "SEC");
	}

	/**
	 * dfs,看完后,想了想,89%,64%
	 */
	boolean[][] flagArr;
	boolean res = false;

	public boolean exist(char[][] board, String word) {
		if (board == null || board.length < 1 || word == null || word.length() < 1) return false;
		flagArr = new boolean[board.length][board[0].length];

		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (board[i][j] == word.charAt(0))//在这的时候,起初想到了bfs,但后续发现bfs和flagArr有点冲突,如ECCE
					dfs(board, word, 0, i, j);
			}
		}

		return res;

	}

	public void dfs(char[][] board, String word, int wordIdx, int i, int j) {
		if (res) return;
		if (word.charAt(wordIdx) != board[i][j]) return;
		if (wordIdx == word.length() - 1) {
			res = true;
			return;
		}

		flagArr[i][j] = true;//1.dosomething
		if (0 <= i - 1 && i - 1 < board.length && flagArr[i - 1][j] == false)
			dfs(board, word, wordIdx + 1, i - 1, j);//2.dfs
		if (0 <= i + 1 && i + 1 < board.length && flagArr[i + 1][j] == false)
			dfs(board, word, wordIdx + 1, i + 1, j);//2.dfs
		if (0 <= j - 1 && j - 1 < board[0].length && flagArr[i][j - 1] == false)
			dfs(board, word, wordIdx + 1, i, j - 1);//2.dfs
		if (0 <= j + 1 && j + 1 < board[0].length && flagArr[i][j + 1] == false)
			dfs(board, word, wordIdx + 1, i, j + 1);//2.dfs
		flagArr[i][j] = false;//3.backTrace
	}
}
